package reviewAlgorithms.search;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SolveNQueens {
    public static void main(String[] args) {
        List<List<String>> res = solveNQueens(4);
        for (List<String> item : res) {
            for (String item1 : item) {
                System.out.println(item1);
            }
            System.out.println("==========");
        }
    }
    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> resStr = new ArrayList<>();
        List<char[][]> res = new ArrayList<>();
        if (n < 1){
            return resStr;
        }
        char[][] location = new char[n][n];
        for (char[] item : location) {
            Arrays.fill(item, '.');
        }
        int index = 0;
        int[][] state = new int[n][n];
        int maxIndex = n*n;
        int queensNum = 0;
        getSolveNQueens(n,queensNum,index,maxIndex,location,state,res);
        for (char[][] item : res) {
            List<String> strings = new ArrayList<>();
            for (char[] item1:item){
                strings.add(new String(item1));
            }
            resStr.add(strings);
        }
        return resStr;
    }

    private static void getSolveNQueens(int n, int queensNum, int index, int maxIndex, char[][] location, int[][] state, List<char[][]> res) {
        if (index >= maxIndex || index / n > queensNum){
            if (queensNum == n){
                char[][] locationTemp = new char[n][n];
                for (int j = 0; j < n; j++) {
                    for (int k = 0; k < n; k++) {
                        locationTemp[j][k] = location[j][k];
                    }
                }
                res.add(locationTemp);
            }
            return;
        }
        int row = index / n;
        int column = index % n;
        if (state[row][column] == 0){
            for (int i = 0; i < 2; i++) {
                if (i == 0){
                    char[][] locationTemp = new char[n][n];
                    int[][] stateTemp = new int[n][n];
                    for (int j = 0; j < n; j++) {
                        for (int k = 0; k < n; k++) {
                            locationTemp[j][k] = location[j][k];
                            stateTemp[j][k] = state[j][k];
                        }
                    }
                    renewState(row,column,location,state);
                    getSolveNQueens(n,queensNum + 1,index + 1,maxIndex,location,state,res);
                    location = locationTemp;
                    state = stateTemp;
                }else {
                    getSolveNQueens(n,queensNum ,index + 1,maxIndex,location,state,res);
                }
            }
        }else {
            getSolveNQueens(n,queensNum ,index + 1,maxIndex,location,state,res);
        }

    }

    private static void renewState(int row, int column, char[][] location, int[][] state) {
        for (int i = 0; i < location.length; i++) {
            state[row][i] = 1;
        }
        for (int i = 0; i < location.length; i++) {
            state[i][column] = 1;
        }
        int i = row;
        int j = column;
        while (i < location.length && j < location.length){
            state[i][j] = 1;
            i ++;
            j ++;
        }
        i = row;
        j = column;
        while (i >= 0 && j >= 0){
            state[i][j] = 1;
            i --;
            j --;
        }
        i = row;
        j = column;
        while (i < location.length && j >= 0){
            state[i][j] = 1;
            i ++;
            j --;
        }
        i = row;
        j = column;
        while (i >= 0 && j < location.length){
            state[i][j] = 1;
            i --;
            j ++;
        }
        location[row][column] = 'Q';
    }
}
